package com.lfg.leetcode.leetcode200;


import com.lfg.leetcode.leetcode0.TreeNode;

import java.util.LinkedList;

public class No297Codec {

    public static void main(String[] args) {

        Codec obj = new Codec();
        String data = "[1,2,3,null,null,4,5]";
        TreeNode node = obj.deserialize(data);

        String serialize = obj.serialize(node);
        System.out.println(data.equals(serialize));

    }
}

class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        LinkedList<TreeNode> nodes = new LinkedList<>();
        LinkedList<TreeNode> list = new LinkedList<>();
        if (null != root) {
            list.add(root);
        }
        StringBuilder ret = new StringBuilder("[");
        while (!list.isEmpty()) {
            nodes = list;
            list = new LinkedList<>();
            int cnt = 0;
            while (!nodes.isEmpty()) {
                TreeNode node = nodes.poll();
                if (ret.length() > 1) {
                    ret.append(",");
                }
                if (node == null) {
                    ret.append("null");
                    continue;
                }
                ret.append(node.val);
                if (node.left != null) {
                    cnt++;
                }
                if (node.right != null) {
                    cnt++;
                }
                list.add(node.left);
                list.add(node.right);
            }
            if (cnt == 0) {
                break;
            }
        }
        ret.append("]");
        return ret.toString();
    }

    public TreeNode deserialize(String content) {
        if (null == content || content.length() == 0) {
            return null;
        }
        content = content.trim();
        content = content.substring(1, content.length() - 1);
        if (content.length() == 0) {
            return null;
        }
        String[] item = content.split(",");
        if (item.length == 0) {
            return null;
        }
        LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();
        TreeNode root = new TreeNode(Integer.parseInt(item[0]));
        nodes.add(root);
        int index = 1;
        while (!nodes.isEmpty()) {
            if (index > item.length) {
                break;
            }
            TreeNode node = nodes.pop();
            if (index < item.length && !"null".equals(item[index])) {
                node.left = new TreeNode(Integer.valueOf(item[index]));
                nodes.add(node.left);
            }
            index++;
            if (index < item.length && !"null".equals(item[index])) {
                node.right = new TreeNode(Integer.valueOf(item[index]));
                nodes.add(node.right);
            }
            index++;
        }
        return root;
    }
}

